home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 18242 < prev    next >
Encoding:
Text File  |  1996-08-05  |  1.7 KB  |  48 lines
  1. Path: ix.netcom.com!news
  2. From: Bradd W. Szonye <bradds@ix.netcom.com>
  3. Newsgroups: comp.lang.c++
  4. Subject: RE: merge sort
  5. Date: 19 Apr 1996 09:40:27 GMT
  6. Organization: Netcom
  7. Message-ID: <01bb2dd4.885af680$c6c2b7c7@Zany.localhost>
  8. References: <4jpqpg$lhj@dub-news-svc-6.compuserve.com> <4jsae3$1a3@bilbo.nask.org.pl> <4juf4c$5gl@news.microsoft.com>
  9. NNTP-Posting-Host: det-mi6-06.ix.netcom.com
  10. X-NETCOM-Date: Fri Apr 19  4:40:27 AM CDT 1996
  11. X-Newsreader: Microsoft Internet News
  12.  
  13.  
  14. On Wednesday, April 03, 1996, Dann Corbit wrote...
  15. > In article <4jsae3$1a3@bilbo.nask.org.pl>, flssoft@blue.maloka.waw.pl
  16. says...
  17. > >
  18. > >Philippe Verdy <100105.3120@compuserve.com> wrote:
  19. > >
  20. > >>PC Lab User <lab-mail@cs.utas.edu.au> s'Θcrit :
  21. > >>> has anyone got some source for the "merge" algorithm used in
  22. mergesort?
  23. > >>> thanx
  24. > >>> 
  25. > >>> m_wookey@postoffice.utas.edu.au
  26. > >>This sort algorithm is of the same general idea as the QuickSort:
  27. > >>Divide and conquer. It is dividing a segment to sort, into two
  28. > >>subsegments to sort.
  29. > >[cut]
  30. > >
  31. > >But note that Marge Sort has O(n) memory cost. Quick Sort has O(1).
  32. > The simplest version of Merge Sort needs n extra pointers.  For
  33. > an array of records, this is typically a small fraction of the 
  34. > actual memory supply needed for the data.  There are some recent
  35. > papers that show an optimal merge sort can run with O(sqrt(n))
  36. > extra pointers.
  37. > -- 
  38. > The opinions expressed in this message are my own personal views
  39. > and do not reflect the official views of Microsoft Corporation.
  40. > In fact, I'm just a subcontractor, not an employee, so pull in your
  41. claws.
  42. > 
  43. > 
  44. Yes, but Mergesort is much better than Quicksort for external sorts
  45. (disk-based sorts) since its memory accesses are less random.
  46.  
  47.  
  48.